IP (Internet protocol) multicast builds multicast distribution trees to deliver packets from senders to receivers. The distribution trees are formed by installing multicast forwarding states on routers in a network. Typically, the multicast forwarding states are difficult to aggregate, hence posting a scalability issue for backbone service providers that need support a relatively large number of multicast groups.
Recently, MPLS (multi-protocol label switching) techniques have been greatly utilized in network routing technologies. In an MPLS network, incoming packets are assigned a “label” by a “label edge router (LER)”. Packets are forwarded along a label switch path (LSP) where each label switch router (LSR) makes forwarding decisions based solely on the contents of the label. At each hop, the LSR strips off the existing label and applies a new label which tells the next hop how to forward the packet.
A label is a short, fixed length, locally significant identifier which is used to identify a FEC (forwarding equivalence class). The label which is put on a particular packet represents the FEC to which that packet is assigned. FEC is a set of packets which will be forwarded in the same manner (e.g., over the same path with the same forwarding treatment). Typically, packets belonging to the same FEC will follow the same path in the MPLS domain. While assigning a packet to an FEC, the ingress LSR may look at the IP header and also some other information such as the interface on which this packet arrived. The FEC to which a packet is assigned is identified by a label.
Label switch paths (LSPs) are established by network operators for a variety of purposes, such as to guarantee a certain level of performance, to route around network congestion, or to create IP tunnels for network-based virtual private networks. In many ways, LSPs are no different than circuit-switched paths in ATM or Frame Relay networks, except that they are not dependent on a particular Layer 2 technology. An LSP is a specific path traffic path through an MPLS network.
An LSP is a set of LSRs that packets belonging to a certain FEC travel in order to reach their destination. Since MPLS allows hierarchy of labels known as a label stack, it is possible to have different LSPs at different levels of labels for a packet to reach its destination. So more formally, a LSP of a packet with a label of level m is a set of LSRs that a packet p has to travel at level m to reach its destination. Further detailed information regarding MPLS can be found in RFC3031, which is herein incorporated by reference in its entirety.
An LSP is provisioned using label distribution protocols (LDPs) such as RSVP-TE (reserved protocol-traffic engineering) or CR-LDP. Either of these protocols will establish a path through an MPLS network and will reserve necessary resources to meet pre-defined service requirements for the data path.
An LDP is a specification that lets a label switch router (LSR) distribute labels to its LDP peers. When a LSR assigns a label to an FEC, it needs to let its relevant peers know of this label and its meaning and LDP is used for this purpose. Since a set of labels from the ingress LSR to the egress LSR in an MPLS domain defines an LSP and since labels are mapping of network layer routing to the data link layer switched paths, LDP helps in establishing a LSP by using a set of procedures to distribute the labels among the LSR peers.
An LSP can be established that crosses multiple Layer 2 transports such as ATM (asynchronous transport mode), Frame Relay or Ethernet. Thus, one of the true promises of MPLS is the ability to create end-to-end circuits, with specific performance characteristics, across any type of transport medium, eliminating the need for overlay networks or Layer 2 only control mechanisms.
A conventional MPLS label stack is a linear data structure. Currently, there are three major operations defined on the label stack: 1) a “push” operation that adds one or more labels onto the label stack; 2) a “swap” operation that replaces a label on the top of the label stack with a new label; 3) a “pop” operation that removes a label on the top of the label stack and process a next label or the next header depending on if this is the bottom of the label stack. In some cases, operations 1) and 2) may be combined to form a “swap and push” operation that replaces a label on the top of the label stack and then pushes one or more new labels onto the label stack.
Although the above techniques work well with a multicast operation having a linear structure, however, these techniques may not work well for a multicast operation having a non-linear structure. As a result, duplicated packets may be transmitted and network traffic may be increased.